package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/21 16:52
 */
public class C169 {

    // 找出多数元素 出现频率在0.5倍以上的
    // 暴力解
    public static int majorityElement(int[] nums) {
        int K = nums.length % 2 == 0 ? nums.length / 2 : nums.length / 2 + 1;
        // 找到连续出现K次的数
        Arrays.sort(nums);
        int i = 0, count = 1;
        for (; i < nums.length - 1; i++) {
            if(nums[i] == nums[i+1]) {
                count ++;
            }else {
                if(count >= K) return nums[i];
                count = 1;
            }
        }
        return count >= K ? nums[i] : -1;
    }

    public static int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];   // 一定存在众数的话, 排好序中间这个数必须得是众数
    }

    // 摩尔投票
    public static int majorityElement3(int[] nums) {
        if(nums == null || nums.length == 0) {
            return -1;
        }
        int candidate = nums[0], count = 1;
        for (int i = 1; i < nums.length; i++) {
            if(count == 0) {
                candidate = nums[i];
                count++;
                continue;
            }
            if(candidate == nums[i]) {
                count++;
            }else {
                count--;
            }
        }
        // 找到了可能出现半数以上的数, 在遍历计数一下看是否正确
        count = 0;
        for (int i : nums) {
            if(i == candidate) {
                count++;
            }
        }
        return count > nums.length/2 ? candidate : -1;
    }


    // for test
    public static void main(String[] args) {
        // 输入：[3,2,3]
        //输出：3
        //输入：[2,2,1,1,1,2,2]
        //输出：2
        int[] nums = {3,2,3};
//        int[] nums = {2,2,1,1,1,2,2};
        System.out.println(majorityElement(nums));
    }

}
